public class Main {
    public static void main(String[] args) {
        // 2 A>B A>C B>C                     2^2-1
        // 3 A>C A>B C>B A>C B>A B>C A>C     2^3-1
//        han(1,'A','B','C');
//        System.out.println();
//        han(2,'A','B','C');
//        System.out.println();
        han(3,'A','B','C');
        System.out.println();
        han(4,'A','B','C');
        System.out.println();
        han(5,'A','B','C');
    }
    public static void move(char pos1, char pos2){
        System.out.print(pos1+"->"+pos2+" ");
    }

    /**
     *
     * @param n 盘子数目
     * @param pos1 起始位置
     * @param pos2 中转位置
     * @param pos3 目的位置
     */
    public static void han(int n, char pos1, char pos2, char pos3){
        if(n == 1){
            move(pos1,pos3);
            return;
        }
        han(n-1, pos1, pos3, pos2);
        move(pos1,pos3);
        han(n-1, pos2, pos1, pos3);
    }
}